# Структура и интерпретация компьютерных программ

В этом разделе приведены решения упражнений, взятых из книги 
["Structure and Interpretation of Computer Programs" авторов Abelson Harold, Sussman Gerald Jay, Sussman Julie][SICP].
Для решения используется Scala.

## Глава 1. Построение абстракций с помощью процедур

## 1.1 Элементы программирования

### 1.1.1 Выражения - 1.1.6 Условные выражения и предикаты

#### 1.1.1 Выражения

Выражения рода `(- 1000 334)`, образуемые путем заключения списка выражений в скобки 
с целью обозначить применение функции к аргументам, называются _комбинациями_ (_combinations_). 
Самый левый элемент в списке называется _оператором_ (_operator_), а остальные элементы — _операндами_ (_operands_). 
Значение комбинации вычисляется путем применения процедуры, задаваемой оператором, к _аргументам_ (_arguments_), которые
являются значениями операндов.
Соглашение, по которому оператор ставится слева от операндов, известно как _префиксная нотация_ (_prefix notation_). 

Префиксная нотация естественным образом расширяется, позволяя комбинациям _вкладываться_ (_nest_) друг в друга, то есть
допускает комбинации, элементы которых сами являются комбинациями: `(+ (* 3 5) (- 10 6))`.

Правила форматирования, при которых всякая длинная комбинация записывается так, чтобы ее операнды выравнивались
вертикально, называются _красивая печать_ (_pretty printing_). Получающиеся отступы ясно показывают структуру выражения.

```
(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))
```

Интерпретатор считывает выражение с терминала, вычисляет его и печатает результат.
Этот способ работы иногда называют _циклом чтение-вычисление-печать_ (_read-eval-print loop_).

#### 1.1.2. Имена и окружение

Одна из важнейших характеристик языка программирования — какие в нем существуют средства использования имен 
для указания на вычислительные объекты.
Мы говорим, что имя обозначает _переменную_ (_variable_), чьим _значением_ (_value_) является объект.

В Scala мы даем вещам имена с помощью слова `val`. 
Предложение `val size 2` заставляет интерпретатор связать значение `2` с именем `size`.

Ясно, что раз интерпретатор способен ассоциировать значения с символами и затем вспоминать их, 
то он должен иметь некоторого рода память, сохраняющую пары имя-объект. 
Эта память называется _окружением_ (_environment_) (а точнее, _глобальным окружением_ (_global environment_)).

#### 1.1.3. Вычисление комбинаций

Чтобы вычислить комбинацию, требуется:

- Вычислить все подвыражения комбинации.
- Применить процедуру, которая является значением самого левого подвыражения (оператора) к аргументам — 
  значениям остальных подвыражений (операндов).

Заметим, что на первом шаге для того, чтобы провести процесс вычисления для комбинации, 
нужно сначала проделать процесс вычисления для каждого элемента комбинации. 
Таким образом, правило вычисления _рекурсивно_ (_recursive_) по своей природе; 
это означает, что в качестве одного из своих шагов оно включает применение того же самого правила.

Форма правила вычисления «распространить значения наверх» является примером общего типа процессов,
известного как _накопление по дереву_ (_tree accumulation_).

Заметим, что многократное применение первого шага приводит нас к такой точке, где нужно вычислять уже не комбинации, 
а элементарные выражения, а именно числовые константы, встроенные операторы или другие имена. 
С этими случаями мы справляемся, положив, что:

- значением числовых констант являются те числа, которые они называют;
- значением встроенных операторов являются последовательности машинных команд, которые выполняют соответствующие операции; и
- значением остальных имен являются те объекты, с которыми эти имена связаны в окружении.

Заметим, что рассмотренное нами правило вычисления не обрабатывает определений.
Например, вычисление `val x 3` не означает применение `val` к двум аргументам, один из которых значение символа `x`, 
а другой равен `3`, поскольку смысл `val` как раз и состоит в том, чтобы связать `x` со значением. 
(Таким образом, `val x 3` — не комбинация.)
Такие исключения из вышеописанного правила вычисления называются _особыми формами_ (_special forms_).

#### 1.1.4. Составные процедуры

- Числа и арифметические операции представляют собой элементарные данные и процедуры.
- Вложение комбинаций дает возможность комбинировать операции.
- Определения, которые связывают имена со значениями, дают ограниченные возможности абстракции.

_Определение процедур_ (_procedure definitions_) — метод абстракции, с помощью которого составной операции можно дать
имя и затем ссылаться на нее как на единое целое.

Например, определение "возведения в квадрат": `def square(x: Int): Int = x * x`

Здесь мы имеем _составную процедуру_ (_compound procedure_), которой дали имя `square`. 
Эта процедура представляет операцию умножения чего-либо само на себя. 

Общая форма определения процедуры такова: `(define (<имя> <формальные-параметры>) <тело>)`.
`<Имя>` — это тот символ, с которым нужно связать в окружении определение процедуры. 
`<Формальные-параметры>` — это имена, которые в теле процедуры используются для отсылки 
к соответствующим аргументам процедуры. 
`<Тело>` — это выражение, которое вычислит результат применения процедуры, 
когда формальные параметры будут заменены аргументами, к которым процедура будет применяться. 
`<Имя>` и `<формальные-параметры>` заключены в скобки, как это было бы при вызове определяемой процедуры.

#### 1.1.5. Подстановочная модель применения процедуры

Для составных процедур процесс вычисления протекает так:

- Чтобы применить составную процедуру к аргументам, требуется вычислить тело процедуры, 
  заменив каждый формальный параметр соответствующим аргументом.

Следующий процесс называется _подстановочной моделью_ (_substitution model_) применения процедуры.

- `(f 5)`, где
    - `def f(a: Int): Int = sumOfSquares(a + 1, a * 2)))`
    - `def sumOfSquares(x: Int, y: Int): Int = square(x) + square(y)`
    - `def square(x: Int): Int = x * x`
- `sumOfSquares(a + 1, a * 2)` - восстанавливаем тело `f`
- `sumOfSquares(5 + 1, 5 * 2)` - заменяем формальный параметр `a` на аргумент `5`
- `sumOfSquares(6, 10)` - вычисляем аргументы
- `square(6) + square(10)` - восстанавливаем тело `sumOfSquares`
- `6 * 6 + 10 * 10` - восстанавливаем тело `square`

##### Аппликативный и нормальный порядки вычисления

В соответствии с описанием из раздела 1.1.3, интерпретатор сначала вычисляет оператор и операнды, 
а затем применяет получившуюся процедуру к получившимся аргументам. 
Но это не единственный способ осуществлять вычисления. 
Другая модель вычисления не вычисляет аргументы, пока не понадобится их значение. 
Вместо этого она подставляет на место параметров выражения-операнды, пока не получит выражение, 
в котором присутствуют только элементарные операторы, и лишь затем вычисляет его. 

Процесс выглядит так:

- `(sum-of-squares (+ 5 1) (* 5 2))`
- `(+ (square (+ 5 1)) (square (* 5 2)))`
- `(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))`

за которыми последуют редукции:

- `(+ (* 6 6) (* 10 10))`
- `(+ 36 100)`
- `136`

Это дает тот же результат, что и предыдущая модель вычислений, но процесс его получения отличается. 
В частности, вычисление `(+ 5 1)` и `(* 5 2)` выполняется здесь по два раза, 
в соответствии с редукцией выражения `(* x x)`, где `x` заменяется, соответственно, на `(+ 5 1)` и `(* 5 2)`.

Альтернативный метод «полная подстановка, затем редукция» известен под названием _нормальный порядок вычислений_ 
(_normal-order evaluation_), в противоположность методу «вычисление аргументов, затем применение процедуры», 
которое называется _аппликативным порядком вычислений_ (_applicative-order evaluation_).

#### 1.1.6. Условные выражения и предикаты

![](https://latex.codecogs.com/svg.image?%7Cx%7C=%5Cbegin%7Bcases%7Dx&%5Ctext%7Bif%5Cquad%7Dx%3E0%5C%5C0&%5Ctext%7Bif%5Cquad%7Dx=0%5C%5C-x&%5Ctext%7Bif%5Cquad%7Dx%3C0%5Cend%7Bcases%7D)

Такая конструкция называется _разбором случаев_ (_case analysis_). 

```dotty
def abs(x: Int): Int =
  if x > 0 then x
  else if x == 0 then 0
  else -x
```

Общая форма условного выражения такова:

```
if <p1> then <e1>
else if <p2> then <e2>
...
else if <pn> then <en>
else <e>
```

Она состоит из символов `if`, `else if`, `else`, за которыми следуют пары выражений (`<pi> <ei>`), называемых _ветвями_ (_clauses_). 
В каждой из этих пар первое выражение — _предикат_ (_predicate_), то есть выражение, 
значение которого интерпретируется как истина или ложь.

Условные выражения вычисляются так: сначала вычисляется предикат `<p1>`. 
Если его значением является ложь, вычисляется `<p2>`. Если значение `<p2>` также ложь, вычисляется `<p3>`. 
Этот процесс продолжается до тех пор, пока не найдется предикат, значением которого будет истина, 
и в этом случае интерпретатор возвращает значение соответствующего _выражения-следствия_ (_consequent expression_) 
в качестве значения всего условного выражения. 
Если ни один из `<pi>` ни окажется истинным, значение условного выражения равно `<e>`.

#### Упражнение 1.1

> Ниже приведена последовательность выражений.
> Какой результат напечатает интерпретатор в ответ на каждое из них?
> Предполагается, что выражения вводятся в том же порядке, в каком они написаны.

```dotty
10                    
// res0: Int = 10                    
(5 + 3 + 4)           
// res1: Int = 12)           
(9 - 1)               
// res2: Int = 8)               
(6 / 2)               
// res3: Int = 3)               
((2 * 4) + (4 - 6))   
// res4: Int = 6)   
val a = 3
// a: Int = 3
val b = a + 1        
// b: Int = 4        
(a + b + (a * b))    
// res5: Int = 19)    
(a == b)             
// res6: Boolean = false)             

if (b > a) && (b < (a * b)) then b else a                  
// res7: Int = 4                  

if a == 4 then 6
else if b == 4 then 6 + 7 + a
else 25                                                    
// res8: Int = 16                                                    
 
2 + (if b > a then b else a)                             
// res9: Int = 6                             

((if a > b then a else if a < b then b else -1) * (a + 1)) 
// res10: Int = 16
```

[Scala worksheet](https://scastie.scala-lang.org/L3tfjiq3SgaRhXroZiYHDw)

#### Упражнение 1.2

> Переведите следующее выражение в префиксную форму:
> \\(\frac{5 + 4 + (2 - (3 - (6 + \frac{4}{5})))}{3(6 - 2)(2 - 7)}\\)

Выражение в префиксной форме выглядит так:

```text
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
```

#### Упражнение 1.3

> Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумму
> квадратов двух больших из них.

```dotty
def square(x: Int): Int = x * x

def sumOfSquares(x: Int, y: Int): Int = square(x) + square(y)

def f(a: Int, b: Int, c: Int): Int =
  if a <= b && a <= c then sumOfSquares(b, c)
  else if b <= c then sumOfSquares(a, c)
  else sumOfSquares(a, b)

f(5, 3, 4)
// res11: Int = 41
```

[Scala worksheet](https://scastie.scala-lang.org/i5pFJYMHTjurWwltcAkjNA)

#### Упражнение 1.4

> Заметим, что наша модель вычислений разрешает существование комбинаций, операторы которых — составные выражения.
> С помощью этого наблюдения опишите, как работает следующая процедура:
>
> ```text
> (define (a-plus-abs-b a b)
>   ((if (> b 0) + -) a b))
> ```

Процедура `a-plus-abs-b` работает так:

- если `b` больше `0`, то выполняется процедура `(+ a b)`
- в ином случае, выполняется процедура `(- a b)`

Эта процедура складывает `a` и модуль числа `b`.

#### Упражнение 1.5

> Бен Битобор придумал тест для проверки интерпретатора на то, с каким порядком вычислений он
> работает, аппликативным или нормальным. Бен определяет такие две процедуры:
>
> ```
> (define (p) (p))
> ```
>
> ```
> (define (test x y)
>   (if (= x 0)
>     0
>     y))
> ```
>
> Затем он вычисляет выражение
>
> ```
> (test 0 (p))
> ```
>
> Какое поведение увидит Бен, если интерпретатор использует аппликативный порядок вычислений?
> Какое поведение он увидит, если интерпретатор использует нормальный порядок?

При аппликативном порядке вычисления результат `(test 0 (p))` не будет получен, 
потому что невозможно вычислить второй аргумент.

При нормально порядке вычисления результат `(test 0 (p))` будет равен `0`, потому что аргументы не вычисляются
и `(test 0 (p))` разложится до:

```
if (= 0 0)
  0
  y
```

, что в свою очередь вернет `0`.

### 1.1.7 Пример: вычисление квадратного корня методом Ньютона

- [Описание метода Ньютона](../algorithms/algorithms/newton.md)
- [Описание метода нахождения квадратного корня](../algorithms/algorithms/numerical.md)
- [Описание метода нахождения кубического корня](../algorithms/algorithms/numerical.md)

#### Упражнение 1.6

> Лиза П. Хакер не понимает, почему `if` должна быть особой формой.
> «Почему нельзя просто определить ее как обычную процедуру с помощью cond?» — спрашивает она.
> Лизина подруга Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версию `if`:
>
> ```
> (define (new-if predicate then-clause else-clause)
>   (cond (predicate then-clause)
>         (else else-clause)))
> ```
>
> Ева показывает Лизе новую программу:
>
> ```
> (new-if (= 2 3) 0 5)
> 5
> (new-if (= 1 1) 0 5)
> 0
> ```
>
> Обрадованная Лиза переписывает через `new-if` программу вычисления квадратного корня:
>
> ```
> (define (sqrt-iter guess x)
>   (new-if (good-enough? guess x)
>           guess
>           (sqrt-iter (improve guess x)
>                      x)))
> ```
>
> Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратных корней?

При аппликативном порядке будут пытаться вычисляться все аргументы процедуры `sqrt-iter`, в том числе и последний,
который использует `sqrt-iter`, а значит процедура войдет в бесконечную рекурсию.

#### Упражнение 1.7

> Проверка `good-enough?`, которую мы использовали для вычисления квадратных корней,
> будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел.
> Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью.
> Поэтому наш тест оказывается неадекватным и для очень больших чисел.
> Альтернативный подход к реализации `good-enough?` состоит в том, чтобы следить,
> как от одной итерации к другой изменяется `guess`,
> и остановиться, когда изменение оказывается небольшой долей значения приближения.
> Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение.
> Верно ли, что на больших и маленьких числах она работает лучше?

Можно предложить следующую реализацию:

```dotty
def goodEnough(guess: Double, next: Double): Boolean = 
  math.abs(guess - next) < 0.001

def average(x: Double, y: Double): Double = (x + y) / 2

def improve(guess: Double, x: Double): Double =
  average(guess, x / guess)

def sqrtIter(guess: Double, x: Double): Double =
  val next = improve(guess, x)
  if goodEnough(guess, next) then guess
  else sqrtIter(next, x)

def sqrt(x: Double): Double = sqrtIter(1.0, x)

sqrt(2.0)
// res12: Double = 1.4142156862745097
sqrt(1000000) 
// res13: Double = 1000.0001533016629
```

[Scala worksheet](https://scastie.scala-lang.org/9m6naSpLQMKkqMvJeGvjNw)

#### Упражнение 1.8

> Метод Ньютона для кубических корней основан на том,
> что если `y` является приближением к кубическому корню из `x`,
> то мы можем получить лучшее приближение по формуле
> \\(\frac{\frac{x}{y^2} + 2y}{3}\\).
>
> С помощью этой формулы напишите процедуру вычисления кубического корня, подобную процедуре для квадратного корня.

Процедура вычисления кубического корня:

```dotty
def square(x: Double): Double = x * x

def goodEnough(guess: Double, next: Double): Boolean = 
  math.abs(guess - next) < 0.001

def improve(guess: Double, x: Double): Double =
  ((x / square(guess)) + 2 * guess) / 3

def cubeIter(guess: Double, x: Double): Double =
  val next = improve(guess, x)
  if goodEnough(guess, next) then next
  else cubeIter(next, x)

def cubeOf(x: Double): Double = cubeIter(1.0, x)

cubeOf(2.0)
// res15: Double = 1.2599210500177698
cubeOf(1000000)
// res16: Double = 100.00000000005313
```

[Scala worksheet](https://scastie.scala-lang.org/MPOYyJyFRoGnIYUbxzTHMw)

### 1.1.8. Процедуры как абстракции типа «черный ящик»

Определение `sqrtIter` _рекурсивно_ (_recursive_); это означает, что процедура определяется в терминах самой себя.

Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи: 
как понять, что очередное приближение нас устраивает, 
как улучшить очередное приближение, и так далее. 
Каждая из этих задач решается с помощью отдельной процедуры. 
Вся программа `sqrt` может рассматриваться как пучок процедур, отражающий декомпозицию задачи на подзадачи.
Важность декомпозиционной стратегии не просто в том, что задача разделяется на части.
Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использована
при определении других процедур. 
Например, когда мы определяем процедуру `goodenough?` с помощью `square`, 
мы можем рассматривать процедуру `square` как «черный ящик». 
В этот момент нас не интересует, как она вычисляет свой результат, — важно
только то, что она способна вычислить квадрат.
Действительно, пока мы рассматриваем процедуру `good-enough?`, `square` — не совсем процедура, 
но скорее абстракция процедуры, так называемая _процедурная абстракция_ (_procedural abstraction_).

##### Локальные имена

У формального параметра особая роль в определении процедуры: не имеет значения, какое у этого параметра имя. 
Такое имя называется _связанной переменной_ (_bound variable_), и мы будем говорить, 
что определение процедуры _связывает_ (_binds_) свои формальные параметры. 
Значение процедуры не изменяется, если во всем ее определении
параметры последовательным образом переименованы. 
Если переменная не связана, мы говорим, что она _свободна_ (_free_). 
Множество выражений, для которых связывание определяет имя, называется _областью действия_ (_scope_) этого имени. 
В определении процедуры связанные переменные, объявленные как формальные параметры процедуры,
имеют своей областью действия тело процедуры.

##### Внутренние определения и блочная структура

Для того чтобы локализовать подпроцедуры, спрятав их внутри `sqrt`, так, 
чтобы `sqrt` могла сосуществовать с другими последовательными приближениями, 
при том что у каждой из них была бы своя собственная процедура `good-enough?`, 
мы разрешаем процедуре иметь внутренние определения, локальные для этой процедуры. 
Например, при решении задачи вычисления квадратного корня мы можем написать:

```dotty
def sqrt(x: Double): Double = 
  def goodEnough(guess: Double, next: Double): Boolean =  math.abs(guess - next) < 0.001

  def average(a: Double, b: Double): Double = (a + b) / 2

  def improve(guess: Double): Double = average(guess, x / guess)

  def sqrtIter(guess: Double): Double =
    val next = improve(guess)
    if goodEnough(guess, next) then guess
    else sqrtIter(next)

  sqrtIter(1.0)

sqrt(2.0)
// res17: Double = 1.4142156862745097
sqrt(1000000) 
// res18: Double = 1000.0001533016629
```

Такое вложение определений, называемое _блочной структурой_ (_block structure_), дает
правильное решение для простейшей задачи упаковки имен. 
Помимо того, что мы можем вложить определения вспомогательных процедур внутрь главной, мы можем их упростить. 
Поскольку переменная `x` связана в определении `sqrt`, процедуры `good-enough?`, `improve` и `sqrt-iter`, 
которые определены внутри `sqrt`, находятся в области действия `x`. 
Таким образом, нет нужды явно передавать `x` в каждую из этих процедур. 
Вместо этого мы можем сделать `x` свободной переменной во внутренних определениях, как это показано ниже. 
Тогда `x` получит свое значение от аргумента, с которым вызвана объемлющая их процедура `sqrt`. 
Такой порядок называется _лексической сферой действия_ (_lexical scoping_) переменных.

## 1.2. Процедуры и порождаемые ими процессы

### 1.2.1. Линейные рекурсия и итерация

Возьмем первый процесс вычисления факториала:

```dotty
def factorial(n: Int): Int =
  if n == 1 then 1
  else n * factorial(n - 1)
  
factorial(6) // 720  
```

[Scala worksheet](https://scastie.scala-lang.org/BfoDRdRaQFaO4fZq0d49Kg)

Подстановочная модель: 

```
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
```

Подстановочная модель показывает сначала серию расширений, а затем сжатие. 
Расширение происходит по мере того, как процесс строит цепочку _отложенных операций_ (_deferred operations_), 
в данном случае цепочку умножений. Сжатие происходит тогда, когда выполняются эти отложенные операции. 
Такой тип процесса, который характеризуется цепочкой отложенных операций, 
называется _рекурсивным процессом_ (_recursive process_). 
Выполнение этого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии. 
При вычислении n! длина цепочки отложенных умножений, а следовательно, и 
объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. 
Такой процесс называется _линейно рекурсивным процессом_ (_linear recursive process_).

Напротив, второй процесс не растет и не сжимается. 

```dotty
def factorial(n: Int): Int =
  factIter(1, 1, n)

def factIter(product: Int, counter: Int, maxCount: Int): Int =
  if counter > maxCount then product
  else factIter(counter * product, counter + 1, maxCount)

factorial(6) // 720
```

[Scala worksheet](https://scastie.scala-lang.org/hI8qxvccRdmIKZEWmA90AA)

Подстановочная модель:

```
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
```

На каждом шаге при любом значении `n` необходимо помнить лишь текущие значения переменных `product`, `counter` и
`max-count`. Такой процесс мы называем _итеративным_ (_iterative process_).

В общем случае, итеративный процесс — это такой процесс, состояние которого
можно описать конечным числом _переменных состояния_ (_state variables_) плюс заранее
заданное правило, определяющее, как эти переменные состояния изменяются от шага к
шагу, и плюс (возможно) тест на завершение, который определяет условия, при которых
процесс должен закончить работу. 
При вычислении n! число шагов линейно растет с ростом n. 
Такой процесс называется _линейно итеративным процессом_ (_linear iterative process_).

#### Упражнение 1.9

> Каждая из следующих двух процедур определяет способ сложения двух положительных целых чисел
> с помощью процедур `inc`, которая добавляет к своему аргументу 1,
> и `dec`, которая отнимает от своего аргумента 1.
>
> ```
> (define (+ a b)
>   (if (= a 0)
>       b
>       (inc (+ (dec a) b))))
> ```
>
> ```
> (define (+ a b)
>   (if (= a 0)
>       b
>       (+ (dec a) (inc b))))
> ```
>
> Используя подстановочную модель, проиллюстрируйте процесс, порождаемый каждой из этих процедур, вычислив `(+ 4 5)`.
> Являются ли эти процессы итеративными или рекурсивными?

Первая функция является рекурсивной и иллюстрируется следующим образом:

```
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
```

Вторая функция - итеративная (при каждом шаге достаточно помнить только два значения - `a` и `b`).
Иллюстрация:

```
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9
```

#### Упражнение 1.10

> Следующая процедура вычисляет математическую функцию, называемую [функцией Аккермана](https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%90%D0%BA%D0%BA%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0).
>
> ```
> (define (A x y)
>   (cond ((= y 0) 0)
>         ((= x 0) (* 2 y))
>         ((= y 1) 2)
>         (else (A (- x 1)
>                  (A x (- y 1))))))
> ```
>
> Каковы значения следующих выражений?
> - `(A 1 10)`
> - `(A 2 4)`
> - `(A 3 3)`

Функцию Аккермана можно определить так:

```dotty
def functionAckermann(x: Int, y: Int): Int =
  if y == 0 then 0
  else if x == 0 then 2 * y
  else if y == 1 then 2
  else functionAckermann(x - 1, functionAckermann(x, y - 1))

functionAckermann(1, 10)
// res19: Int = 1024
functionAckermann(2, 4)
// res20: Int = 65536
functionAckermann(3, 3)
// res21: Int = 65536
```

> Рассмотрим следующие процедуры, где `A` — процедура, определенная выше:
> - `(define (f n) (A 0 n))`
> - `(define (g n) (A 1 n))`
> - `(define (h n) (A 2 n))`
>
> Дайте краткие математические определения функций, вычисляемых процедурами `f`, `g` и `h` для положительных целых значений `n`.

Для малых `x` функция Аккермана равносильна следующим функциям:

- `f <=> 2*n`
- `g <=> 2^n`
- `h <=> 2^2^...^2 (n раз)`

[Scala worksheet](https://scastie.scala-lang.org/AaBfKhBDTI6LT8PayhkQlg)


### 1.2.2. Древовидная рекурсия

Существует еще одна часто встречающаяся схема вычислений, называемая _древовидная рекурсия_ (_tree recursion_). 
В качестве примера рассмотрим вычисление последовательности чисел Фибоначчи, 
в которой каждое число является суммой двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Общее правило для чисел Фибоначчи можно сформулировать так:

![](https://latex.codecogs.com/svg.image?%20Fib(n)=%5Cbegin%7Bcases%7D0&%5Ctext%7Bif%20x=0%7D%5C%5C1&%5Ctext%7Bif%20x=1%7D%5C%5CFib(n-1)&plus;Fib(n-2)&%5Ctext%7B%7D%5Cend%7Bcases%7D)

Можно немедленно преобразовать это определение в процедуру:

```
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
```



#### Упражнение 1.11

> Функция `f` определяется правилом: `f(n) = n`, если `n < 3`,
> и `f(n) = f(n − 1) + f(n − 2) + f(n − 3)`, если `n ≥ 3`.
>
> Напишите процедуру, вычисляющую `f` с помощью рекурсивного процесса.
>
> Напишите процедуру, вычисляющую `f` с помощью итеративного процесса.

Рекурсивный процесс:

```dotty
def recursion(n: Int): Int =
  if n < 3 then n
  else recursion(n - 1) + recursion(n - 2) + recursion(n - 3)
```

Итеративный процесс:

```dotty
def iteration(n: Int): Int =
  def loop(a: Int, b: Int, c: Int, count: Int): Int =
    if count == 0 then c
    else loop(a + b + c, a, b, count - 1)
  loop(2, 1, 0, n)
```

[Scala worksheet](https://scastie.scala-lang.org/H7ln1CFmTrusvslOjsHgBw)

#### Упражнение 1.12

> Приведенная ниже таблица называется треугольником Паскаля (Pascal’s triangle):
>
> 1
>
> 1 1
>
> 1 2 1
>
> 1 3 3 1
>
> 1 4 6 4 1
>
> . . .
>
> Все числа по краям треугольника равны `1`,
> а каждое число внутри треугольника равно сумме двух чисел над ним.
>
> Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощью рекурсивного процесса.

```dotty
def pascalsTriangle(n: Int, k: Int): Int =
  if n == 0 || k == n || k == 0 then 1
  else pascalsTriangle(n - 1, k - 1) + pascalsTriangle(n - 1, k)

pascalsTriangle(4, 2)
// res22: Int = 6
```

[Scala worksheet](https://scastie.scala-lang.org/qxmgWhSsS2exUsfTtboTkA)

#### Упражнение 1.13

> Докажите, что Fib(n) есть целое число, ближайшее к \\(\frac{\varphi^{n}}{\sqrt{5}}\\),
> где \\(\varphi = \frac{1 + \sqrt{5}}{2}\\).
>
> Указание: пусть \\(\psi = \frac{1 - \sqrt{5}}{2}\\).
> С помощью определения чисел Фибоначчи и индукции докажите,
> что Fib(n) = \\(\frac{\varphi^{n} - \psi^{n}}{\sqrt{5}} \\).

Доказательство:

- Заметим, что \\(\varphi^{2} = \varphi^{1} + 1\\):
    - \\(\varphi^{2} = \frac{(1 + \sqrt{5})^{2}}{4} = \frac{6 + 2\sqrt{5}}{4} = 1 + \frac{2 + 2\sqrt{5}}{4} = 1 + \varphi\\)
- а также, что \\(\psi^{2} = \psi^{1} + 1\\):
    - \\(\psi^{2} = \frac{(1 - \sqrt{5})^{2}}{4} = \frac{6 - 2\sqrt{5}}{4} = 1 + \frac{2 - 2\sqrt{5}}{4} = 1 + \psi\\)
- n == 0, тогда \\(Fib(0) = \frac{\varphi^{0} − \psi^{0}}{\sqrt{5}} = \frac{1 − 1}{\sqrt{5}} = 0\\) - верно.
- n > 0,
    - Fib(n) =
    - Fib(n - 1) + Fib(n - 2) =
    - \\(\frac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\varphi^{n-2} - \psi^{n-2}}{\sqrt{5}} = \\)
    - \\(\frac{(\varphi^{n-1} + \varphi^{n-2}) - (\psi^{n-1} + \psi^{n-2})}{\sqrt{5}} = \\)
    - \\(\frac{(\varphi^{n-2}(1 + \varphi)) - (\psi^{n-2}(1 + \psi))}{\sqrt{5}} = \\)
    - \\(\frac{\varphi^{n-2}\*\varphi^{2} - \psi^{n-2}\*\psi^{2}}{\sqrt{5}} = \\)
    - \\(\frac{\varphi^{n} - \psi^{n}}{\sqrt{5}} \\)


### 1.2.3. Порядки роста

Предшествующие примеры показывают, что процессы могут значительно различаться
по количеству вычислительных ресурсов, которые они потребляют. Удобным способом
описания этих различий является понятие _порядка роста_ (_order of growth_), которое дает
общую оценку ресурсов, необходимых процессу при увеличении его входных данных.

Пусть n — параметр, измеряющий размер задачи, и пусть R(n) — количество ресурсов, 
необходимых процессу для решения задачи размера n.

Мы говорим, что R(n) имеет порядок роста Θ(f(n)), что записывается R(n) = Θ(f(n)) и произносится «тета от f(n)», 
если существуют положительные постоянные \\(k\_1\\) и \\(k\_2\\), независимые от n, 
такие, что \\(k\_1 \times f(n) \leq R(n) \leq k\_2 \times f(n)\\) для всякого достаточно большого n. 
(Другими словами, значение R(n) заключено между \\(k\_1 \times f(n)\\) и \\(k\_2 \times f(n)\\).)

#### Упражнение 1.14

> Нарисуйте дерево, иллюстрирующее процесс,
> который порождается процедурой `count-change` из раздела 1.2.2 при размене `11` центов.
>
> ```dotty
> def countChange(amount: Int): Int =
>   def firstDenomination(kindOfCoins: Int): Int =
>     if kindOfCoins == 1 then 1
>     else if kindOfCoins == 2 then 5
>     else if kindOfCoins == 3 then 10
>     else if kindOfCoins == 4 then 25
>     else 50
> 
>   def cc(amount: Int, kindOfCoins: Int): Int =
>     if amount == 0 then 1
>     else if amount < 0 || kindOfCoins == 0 then 0
>     else
>       cc(amount, kindOfCoins - 1) +
>         cc(amount - firstDenomination(kindOfCoins), kindOfCoins)
> 
>   cc(amount, 5)
> 
> countChange(100) // 292
> ```
>
> Каковы порядки роста памяти и числа шагов,
> используемых этим процессом при увеличении суммы, которую требуется разменять?

Поддерево `cc 6 1`:

- `cc 6 1`
    - `cc 6 0`
        - `0`
    - `cc 5 1`
        - `cc 5 0`
            - `0`
        - `cc 4 1`
            - `cc 4 0`
                - `0`
            - `cc 3 1`
                - `cc 3 0`
                    - `0`
                - `cc 2 1`
                    - `cc 2 0`
                        - `0`
                    - `cc 1 1`
                        - `cc 1 0`
                            - `0`
                        - `cc 0 1`
                            - `1`


Дерево `count-change 11`:

- `cc 11 5`
    - `cc 11 4`
        - `cc 11 3`
            - `cc 11 2`
                - `cc 11 1`
                    - `cc 11 0`
                        - `0`
                    - `cc 10 1`
                        - `cc 10 0`
                            - `0`
                        - `cc 9 1`
                            - `cc 9 0`
                                - `0`
                            - `cc 8 1`
                                - `cc 8 0`
                                    - `0`
                                - `cc 7 1`
                                    - `cc 7 0`
                                        - `0`
                                    - Поддерево `cc 6 1`
                - `cc 6 2`
                    - Поддерево `cc 6 1`
                    - `cc 1 2`
                        - `cc 1 1`
                            - `cc 1 0`
                                - `0`
                            - `cc 0 1`
                                - `1`
                        - `cc -4 2`
                            - `0`
            - `cc 1 3`
                - `cc 1 2`
                    - `cc 1 1`
                        - `cc 1 0`
                            - `0`
                        - `cc 0 1`
                            - `1`
                    - `cc -4 2`
                        - `0`
                - `cc -9 3`
                    - `0`
        - `cc -14 4`
            - `0`
    - `cc -39 5`
        - `0`

Порядки роста памяти и числа шагов равны \\(\Theta (n^2)\\).

#### Упражнение 1.15

> Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением `sin x ≈ x` при малых `x`
> и употребить тригонометрическое тождество \\(sin(x) = 3sin(\frac{x}{3}) - 4sin^{3}(\frac{x}{3})\\)
> для уменьшения значения аргумента `sin`.
> (В этом упражнении будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.)
>
> Эта идея используется в следующих процедурах:
>
> ```
> (define (cube x) (* x x x))
> 
> (define (p x) (- (* 3 x) (* 4 (cube x))))
> 
> (define (sine angle)
>    (if (not (> (abs angle) 0.1))
>        angle
>        (p (sine (/ angle 3.0)))))
> ```
>
> а. Сколько раз вызывается процедура `p` при вычислении `(sine 12.15)`?
>
> б. Каковы порядки роста в терминах количества шагов и используемой памяти (как функция `a`) для процесса,
> порождаемого процедурой `sine` при вычислении `(sine a)`?

На Scala эта программа будет выглядеть так:

```dotty
def cube(x: Double): Double = x * x * x

def p(x: Double): Double =
  3 * x - 4 * cube(x)

def sine(angle: Double): Double =
  if math.abs(angle) <= 0.1 then angle
  else p(sine(angle / 3.0))

sine(12.15)
// res23: Double = -0.39980345741334
```

а) Процедура `p` будет вызываться `roundUp(12.15 / 3) = 5` раз.

б) Количество шагов будет равняться `2 * roundUp(a / 3)`, столько же будет использование памяти.

[Scala worksheet](https://scastie.scala-lang.org/4qEcEUi1Q7GDvTDGrkAbQQ)

### 1.2.4. Возведение в степень

Метод возведения в степень с логарифмической сложностью:

```dotty
def isEven(n: Int): Boolean = n % 2 == 0

def square(n: Int): Int = n * n

def fastExpt(b: Int, n: Int): Int =
  if n == 0 then 1
  else if isEven(n) then square(fastExpt(b, n / 2))
  else b * fastExpt(b, n - 1)
```

#### Упражнение 1.16

> Напишите процедуру, которая развивается в виде итеративного процесса
> и реализует возведение в степень за логарифмическое число шагов, как `fast-expt`.
> (Указание: используя наблюдение, что \\((b^{n/2})^{2} = (b^{2})^{n/2} \\),
> храните, помимо значения степени `n` и основания `b`, дополнительную переменную состояния `a`,
> и определите переход между состояниями так, чтобы произведение \\((ab)^{n}\\) от шага к шагу не менялось.
> Вначале значение `a` берется равным `1`, а ответ получается как значение `a` в момент окончания процесса.
> В общем случае метод определения инварианта (_invariant quantity_),
> который не изменяется при переходе между шагами,
> является мощным способом размышления о построении итеративных алгоритмов.)

На Scala эта программа будет выглядеть так:

```dotty
def power(b: Long, n: Long): BigInt =
  @scala.annotation.tailrec
  def loop(base: BigInt, power: Long, acc: BigInt): BigInt =
    if power == 0 then acc
    else if power % 2 == 0 then loop(base * base, power / 2, acc)
    else loop(base, power - 1, base * acc)
  loop(b, n, 1)

power(2, 10)
// res24: BigInt = 1024
```

[Scala worksheet](https://scastie.scala-lang.org/Vwu5s7IbS8upuU83PIWiJA)


#### Упражнение 1.17

> Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении.
> Подобным же образом можно производить умножение с помощью повторяющегося сложения.
> Следующая процедура умножения (в которой предполагается, что наш язык способен только складывать, но не умножать)
> аналогична процедуре `expt`:
>
> ```
> (define (* a b)
>   (if (= b 0)
>       0
>       (+ a (* a (- b 1)))))
> ```
>
> Этот алгоритм затрачивает количество шагов, линейно пропорциональное `b`.
> Предположим теперь, что, наряду со сложением, у нас есть операции `double`, которая удваивает целое число,
> и `halve`, которая делит (четное) число на `2`.
> Используя их, напишите процедуру, аналогичную `fast-expt`, которая затрачивает логарифмическое число шагов.

На Scala эта программа будет выглядеть так:

```dotty
def double(n: Long): Long = n << 1

def halve(n: Long): Long = n >> 1

def fastMul(a: Long, b: Long): Long =
  if b == 0 then 0L
  else if b % 2 == 0 then double(fastMul(a, halve(b)))
  else a + fastMul(a, b - 1)

fastMul(22, 10)
// res25: Long = 220L
```

[Scala worksheet](https://scastie.scala-lang.org/v7bXGTUPRpi6YMrDC7LnUg)

#### Упражнение 1.18

> Используя результаты упражнений 1.16 и 1.17, разработайте процедуру,
> которая порождает итеративный процесс для умножения двух чисел с помощью сложения, удвоения и деления пополам,
> и затрачивает логарифмическое число шагов.

На Scala эта программа будет выглядеть так:

```dotty
def double(n: Long): Long = n << 1

def halve(n: Long): Long = n >> 1

def fastMul(a: Long, b: Long): Long =
  @scala.annotation.tailrec
  def loop(base: Long, times: Long, acc: Long): Long =
    if times == 0 then acc
    else if times % 2 == 0 then loop(double(base), halve(times), acc)
    else loop(base, times - 1, base + acc)
  loop(a, b, 0)

fastMul(22, 10)
// res27: Long = 220L
```

[Scala worksheet](https://scastie.scala-lang.org/MNMMlUBVTuejpjevIBuz3g)

#### Упражнение 1.19

> Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов.
> Вспомните трансформацию переменных состояния \\(a\\) и \\(b\\) процесса \\(fib-iter\\) из раздела 1.2.2:
> \\(a ← a + b\\) и \\(b ← a\\).
> Назовем эту трансформацию \\(T\\) и заметим, что \\(n\\)-кратное применение \\(T\\), начиная с \\(1\\) и \\(0\\),
> дает нам пару \\(Fib(n + 1)\\) и \\(Fib(n)\\).
> Другими словами, числа Фибоначчи получаются путем применения \\(T^{n}\\),
> \\(n\\)-ой степени трансформации \\(T\\), к паре \\((1,0)\\).
> Теперь рассмотрим \\(T\\) как частный случай \\(p = 0\\), \\(q = 1\\) в семействе трансформаций \\(T\_{pq}\\),
> где \\(T\_{pq}\\) преобразует пару \\((a,b)\\) по правилу \\(a ← bq + aq + ap\\), \\(b ← bp + aq\\).
>
> Покажите, что двукратное применение трансформации \\(T\_{pq}\\)
> равносильно однократному применению трансформации \\(T\_{p′q′}\\) того же типа,
> и вычислите \\(p′\\) и \\(q′\\) через \\(p\\) и \\(q\\).
> Это дает нам прямой способ возводить такие трансформации в квадрат,
> и таким образом, мы можем вычислить \\(T^{n}\\) с помощью последовательного возведения в квадрат,
> как в процедуре \\(fast-expt\\).
> Используя все эти идеи, завершите следующую процедуру, которая дает результат за логарифмическое число шагов:
>
> ```
> (define (fib n)
>   (fib-iter 1 0 0 1 n))
> 
> (define (fib-iter a b p q count)
>   (cond ((= count 0) b)
>         ((even? count)
>           (fib-iter a
>                     b
>                     <??> ; вычислить p’
>                     <??> ; вычислить q’
>                     (/ count 2)))
>         (else (fib-iter (+ (* b q) (* a q) (* a p))
>                         (+ (* b p) (* a q))
>                         p
>                         q
>                         (- count 1)))))
> ```

Применим трансформацию два раза:

- \\(a\_{2} ← b\_{1}q + a\_{1}q + a\_{1}p ← (b\_{0}p + a\_{0}q)q + (b\_{0}q + a\_{0}p + a\_{0}q)(q + p) ← b\_{0}(2pq + q^{2}) + a\_{0}(q^{2} + (p + q)^{2})\\)
- \\(b\_{2} ← b\_{1}p + a\_{1}q ← (b\_{0}p + a\_{0}q)p + (b\_{0}q + a\_{0}p + a\_{0}q)q ← b\_{0}(p^{2} + q^{2}) + a\_{0}(2pq + q^{2})\\)

Представим, что \\(p′ = p^{2} + q^{2}\\) и \\(q′ = 2pq + q^{2}\\). Тогда

- \\(a\_{2} ← b\_{0}q′ + a\_{0}(p′ + q′)\\)
- \\(b\_{2} ← b\_{0}p′ + a\_{0}q′\\)

Это означает, что \\((T\_{pq})^{2} = T\_{p′q′}\\)

Что позволяет реализовать программу так:

```dotty
def fastFib(n: Int): BigInt =
  @scala.annotation.tailrec
  def loop(a: BigInt, b: BigInt, p: BigInt, q: BigInt, count: Int): BigInt =
    if count == 0 then b
    else if count % 2 == 0 then
      loop(a, b, p * p + q * q, 2 * p * q + q * q, count / 2)
    else loop(b * q + a * (p + q), b * p + a * q, p, q, count - 1)

  loop(1, 0, 0, 1, n)

fastFib(30)
// res28: BigInt = 832040
```

[Scala worksheet](https://scastie.scala-lang.org/B4ptJqqXS3CEsvtC9rsHtw)


### 1.2.5. Нахождение наибольшего общего делителя

Вычисление НОД с помощью алгоритма Евклида:

```dotty
@annotation.tailrec
def gcd(a: Int, b: Int): Int =
  if b == 0 then a else gcd(b, a % b)
  
gcd(4851, 3003) // 231   
```

#### Упражнение 1.20

> Процесс, порождаемый процедурой, разумеется, зависит от того, по каким правилам работает интерпретатор.
> В качестве примера рассмотрим итеративную процедуру **gcd**, приведенную выше.
> Предположим, что мы вычисляем эту процедуру с помощью нормального порядка, описанного в разделе 1.1.5.
> (Правило нормального порядка вычислений для **if** описано в упражнении 1.5.)
> Используя подстановочную модель для нормального порядка, проиллюстрируйте процесс,
> порождаемый при вычислении **(gcd 206 40)** и укажите, какие операции вычисления остатка действительно выполняются.
> Сколько операций **remainder** выполняется на самом деле при вычислении **(gcd 206 40)** в нормальном порядке?
> При вычислении в аппликативном порядке?

```
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
```

Нормальный порядок:

```
gcd 206 40

if (= 40 0)
   206
   (gcd 40 (remainder 206 40))

gcd 40 (remainder 206 40)

if (= (remainder 206 40) 0)                   // +1
   40
   (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))    

gcd (remainder 206 40) (remainder 40 (remainder 206 40)) 

if (= (remainder 40 (remainder 206 40)) 0)    // +2
   (remainder 206 40)
   (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))    

Пусть a = (remainder 40 (remainder 206 40)), b = (remainder (remainder 206 40) a)

gcd a b 

if (= b 0)                                    // +4
   a
   (gcd b c)

, где c = reminder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

gcd b c

if (= c 0)                                   // +7
   2
   (gcd c (reminder b c))

2
```

Итого, 14 вычислений при нормальном порядке.

Аппликативный порядок:

```
if (= 40 0)
   206
   (gcd 40 (remainder 206 40))

gcd 40 (remainder 206 40)     // +1

gcd 40 6

if (= 6 0)
   40
   (gcd 6 (remainder 40 6))    

gcd 6 (remainder 40 6)        // +1

gcd 6 4

if (= 4 0)
   6
   (gcd 4 (remainder 6 4))    

gcd 4 (remainder 6 4)         // +1

gcd 4 2

if (= 2 0)
   4
   (gcd 2 (remainder 4 2))

gcd 2 (remainder 4 2)         // +1

gcd 2 0

if (= 0 0)
   2
   (gcd 0 (remainder 2 0))

2   
```

Итого, всего 5 вычислений при аппликативном порядке.

### 1.2.6. Пример: проверка на простоту

#### Упражнение 1.21

> С помощью процедуры **smallest-divisor** найдите наименьший делитель следующих чисел: **199**, **1999**, **19999**.

Решение на Scala:

```dotty
def divides(a: Long, b: Long): Boolean = a % b == 0

def findDivisor(n: Long, d: Long): Long =
  if d * d > n then n
  else if divides(n, d) then d
  else findDivisor(n, d + 1)

def smallestDivisor(n: Long): Long = findDivisor(n, 2)

smallestDivisor(199)   
// res29: Long = 199L   
smallestDivisor(1999) 
// res30: Long = 1999L 
smallestDivisor(19999)
// res31: Long = 7L
```

[Scala worksheet](https://scastie.scala-lang.org/1kSbB13fQhG0DhEOngZFEQ)


#### Упражнение 1.22

> Большая часть реализаций Лиспа содержат элементарную процедуру **runtime**, которая возвращает целое число,
> показывающее, как долго работала система (например, в миллисекундах).
> Следующая процедура **timed-prime-test**, будучи вызвана с целым числом **n**, печатает **n** и проверяет, простое ли оно.
> Если **n** простое, процедура печатает три звездочки и количество времени, затраченное на проверку.
>
> ```
> (define (timed-prime-test n)
>   (newline)
>   (display n)
>   (start-prime-test n (runtime)))
> 
> (define (start-prime-test n start-time)
>   (if (prime? n)
>       (report-prime (- (runtime) start-time))))
> 
> (define (report-prime elapsed-time)
>   (display " *** ")
>   (display elapsed-time))
> ```
>
> Используя эту процедуру, напишите процедуру **search-for-primes**,
> которая проверяет на простоту все нечетные числа в заданном диапазоне.
>
> С помощью этой процедуры найдите наименьшие три простых числа после **1000**;
> после **10 000**; после **100 000**; после **1 000 000**.
>
> Посмотрите, сколько времени затрачивается на каждое простое число.
> Поскольку алгоритм проверки имеет порядок роста **Θ(√n)**, Вам следовало бы ожидать,
> что проверка на простоту чисел, близких к **10 000**,
> занимает в **√10** раз больше времени, чем для чисел, близких к **1000**.
>
> Подтверждают ли это Ваши замеры времени?
>
> Хорошо ли поддерживают предсказание **√n** данные для **100 000** и **1 000 000**?
>
> Совместим ли Ваш результат с предположением,
> что программы на Вашей машине затрачивают на выполнение задач время, пропорциональное числу шагов?

На Scala эта программа будет выглядеть так:

```dotty
import java.time.Instant

def divides(a: Long, b: Long): Boolean = a % b == 0

def findDivisor(n: Long, d: Long): Long =
  if d * d > n then n
  else if divides(n, d) then d
  else findDivisor(n, d + 1)

def smallestDivisor(n: Long): Long = findDivisor(n, 2)

def isPrime(n: Long): Boolean = smallestDivisor(n) == n

def reportPrime(elapsedTime: Long): Unit =
  println(" *** ")
  println(s"${elapsedTime} ms")

def startPrimeTest(n: Long, startTime: Long): Option[Long] =
  if isPrime(n) then
    println(s"n = $n")
    reportPrime(Instant.now().toEpochMilli - startTime)
    Some(n)
  else None

def timedPrimeTest(n: Long): Option[Long] =
  startPrimeTest(n, Instant.now().toEpochMilli())

def searchForPrimes(start: Long, end: Long): Seq[Long] =
  (start to end).flatMap(timedPrimeTest)

searchForPrimes(1000, 1000 + 1000)        // Vector(1009, 1013, 1019, ...)
searchForPrimes(10000, 10000 + 1000)      // Vector(10007, 10009, 10037, ...)
searchForPrimes(100000, 100000 + 1000)    // Vector(100003, 100019, 100043, ...)
searchForPrimes(1000000, 1000000 + 1000)  // Vector(1000003, 1000033, 1000037, ...)
```

[Scala worksheet](https://scastie.scala-lang.org/JOA2TWkATHiF4t3P9V7l8Q)


#### Упражнение 1.23

> Процедура **smallest-divisor** в начале этого раздела проводит множество лишних проверок:
> после того, как она проверяет, делится ли число на **2**, нет никакого смысла проверять делимость на другие четные числа.
> Таким образом, вместо последовательности **2, 3, 4, 5, 6...**, используемой для **test-divisor**,
> было бы лучше использовать **2, 3, 5, 7, 9...**.
>
> Чтобы реализовать такое улучшение, напишите процедуру **next**, которая имеет результатом **3**,
> если получает **2** как аргумент, а иначе возвращает свой аргумент плюс **2**.
> Используйте **(next test-divisor)** вместо **(+ test-divisor 1)** в **smallest-divisor**.
>
> Используя процедуру **timed-prime-test** с модифицированной версией **smallest-divisor**,
> запустите тест для каждого из **12** простых чисел, найденных в упражнении **1.22**.
> Поскольку эта модификация снижает количество шагов проверки вдвое, Вы должны ожидать двукратного ускорения проверки.
> Подтверждаются ли эти ожидания?
> Если нет, то каково наблюдаемое соотношение скоростей двух алгоритмов, и как Вы объясните то, что оно отличается от 2?

На Scala эта программа будет выглядеть так:

```dotty
def divides(a: Long, b: Long): Boolean = a % b == 0

def next(a: Long): Long =
  if a == 2 then 3 else a + 2

def findDivisor(n: Long, d: Long): Long =
  if d * d > n then n
  else if divides(n, d) then d
  else findDivisor(n, next(d))

def smallestDivisor(n: Long): Long = findDivisor(n, 2)

def isPrime(n: Long): Boolean = smallestDivisor(n) == n

Seq(1009, 1013, 1019, 10007, 10009, 10037, 100003, 100019, 100043, 1000003,
  1000033, 1000037).forall(isPrime)
// res33: Boolean = true  
```

[Scala worksheet](https://scastie.scala-lang.org/xE0njNosQWK9zjDUHgw7aQ)


#### Упражнение 1.24

> Модифицируйте процедуру **timed-prime-test** из упражнения 1.22 так,
> чтобы она использовала **fast-prime?** (метод Ферма) и проверьте каждое из 12 простых чисел, найденных в этом упражнении.
> Исходя из того, что у теста Ферма порядок роста **Θ(log n)**,
> то какого соотношения времени Вы бы ожидали между проверкой на простоту поблизости от **1 000 000** и поблизости от **1000**.
> Подтверждают ли это Ваши данные?
> Можете ли Вы объяснить наблюдаемое несоответствие, если оно есть?

На Scala эта программа будет выглядеть так:

```dotty
import java.time.Instant
import scala.util.Random

@annotation.tailrec
def isProbablyPrime(p: Long, max_test: Int): Boolean =
  (max_test <= 0) || {
    (BigInt(Random.nextLong(p)).modPow(p - 1, p) == 1) &&
    isProbablyPrime(p, max_test - 1)
  }

def reportPrime(elapsedTime: Long): Unit =
  println(" *** ")
  println(s"${elapsedTime} ms")

def startPrimeTest(n: Long, startTime: Long): Option[Long] =
  if isProbablyPrime(n, 10) then
    println(s"n = $n")
    reportPrime(Instant.now().toEpochMilli - startTime)
    Some(n)
  else None

def timedPrimeTest(n: Long): Option[Long] =
  startPrimeTest(n, Instant.now().toEpochMilli())
```

[Scala worksheet](https://scastie.scala-lang.org/RS80pTdYSR2Q9ErgcLHo4w)


#### Упражнение 1.25

> Лиза П. Хакер жалуется, что при написании **expmod** мы делаем много лишней работы.
> В конце концов, говорит она, раз мы уже знаем, как вычислять степени, можно просто написать
>
> ```
> (define (expmod base exp m)
>   (remainder (fast-expt base exp) m))
> ```
>
> Права ли она? Стала бы эта процедура столь же хорошо работать при проверке простых чисел?
> Объясните.

Стала бы работать медленнее по причине того, что много времени (и памяти) уходило бы на вычисление "больших" чисел.


#### Упражнение 1.26

> У Хьюго Дума большие трудности в упражнении 1.24. Процедура **fast-prime?** у него работает медленнее, чем **prime?**.
> Хьюго просит помощи у своей знакомой Евы Лу Атор.
> Вместе изучая код Хьюго, они обнаруживают, что тот переписал процедуру **expmod**
> с явным использованием умножения вместо того, чтобы вызывать **square**:
>
> ```
> (define (expmod base exp m)
>   (cond ((= exp 0) 1)
>         ((even? exp)
>          (remainder (* (expmod base (/ exp 2) m)
>                        (expmod base (/ exp 2) m))
>                     m))
>         (else
>          (remainder (* base (expmod base (- exp 1) m))
>                     m))))
> ```
>
> Хьюго говорит: «Я не вижу здесь никакой разницы».
> «Зато я вижу, — отвечает Ева. —
> Переписав процедуру таким образом, ты превратил процесс порядка **Θ(log n)** в процесс порядка **Θ(n)**».
> Объясните

Потому что при использовании процедуры **square** аргумент процедуры **(expmod base (/ exp 2) m)** вычислялся
только 1 раз, а в версии Хьюго - эта же процедура вычисляется два раза (каждый множитель по разу).

Проблемы можно было бы избежать, определив переменную для **(expmod base (/ exp 2) m)**:

```
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         define a (expmod base (/ exp 2) m)
         (remainder (* a a)
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
```


#### Упражнение 1.27

> Покажите, что числа Кармайкла, перечисленные в сноске 47, действительно «обманывают» тест Ферма:
> напишите процедуру, которая берет целое число \\(n\\) и проверяет, правда ли \\(a^{n}\\)
> равняется \\(a\\) по модулю \\(n\\) для всех \\(a < n\\), и проверьте эту процедуру на этих числах Кармайкла.

На Scala эта программа будет выглядеть так:

```dotty
def expmod(base: Long, exp: Long, m: Long): Long =
  if exp == 0 then 1
  else if exp % 2 == 0 then
    val a = expmod(base, exp / 2, m)
    a * a % m
  else
    val a = base * expmod(base, exp - 1, m)
    a % m

def fermatTest(n: Long): Boolean =
  (2L until n).forall(a => expmod(a, n, n) == a)

fermatTest(561)   // true  
fermatTest(1105)  // true 
fermatTest(1729)  // true 
fermatTest(2465)  // true 
fermatTest(2821)  // true 
fermatTest(6601)  // true 
```

[Scala worksheet](https://scastie.scala-lang.org/YAeohITfTfCb1kwDB9VNGw)


#### Упражнение 1.28

> Один из вариантов теста Ферма, который невозможно обмануть,
> называется *тест Миллера–Рабина* (Miller-Rabin test) (Miller 1976; Rabin 1980).
> Он основан на альтернативной формулировке Малой теоремы Ферма, которая состоит в том,
> что если \\(n\\) — простое число, а \\(a\\) — произвольное положительное целое число, меньшее \\(n\\),
> то \\(a\\) в \\(n − 1\\)-ой степени равняется \\(1\\) по модулю \\(n\\).
>
> Проверяя простоту числа \\(n\\) методом Миллера–Рабина, мы берем случайное число \\(a < n\\)
> и возводим его в \\(n − 1\\)-ю степень по модулю \\(n\\) с помощью процедуры \\(expmod\\).
> Однако когда в процедуре `expmod` мы проводим возведение в квадрат,
> мы проверяем, не нашли ли мы «нетривиальный квадратный корень из \\(1\\) по модулю \\(n\\)»,
> то есть число, не равное \\(1\\) или \\(n − 1\\), квадрат которого по модулю \\(n\\) равен \\(1\\).
> Можно доказать, что если такой нетривиальный квадратный корень из \\(1\\) существует, то \\(n\\) - не простое число.
> Можно, кроме того, доказать, что если \\(n\\) — нечетное число, не являющееся простым,
> то по крайней мере для половины чисел \\(a < n\\) вычисление \\(a^{n−1}\\)
> с помощью такой процедуры обнаружит нетривиальный квадратный корень из \\(1\\) по модулю \\(n\\)
> (вот почему тест Миллера–Рабина невозможно обмануть).
>
> Модифицируйте процедуру \\(expmod\\) так, чтобы она сигнализировала обнаружение нетривиального квадратного корня из \\(1\\),
> и используйте ее для реализации теста Миллера–Рабина с помощью процедуры, аналогичной \\(fermat-test\\).
> Проверьте свою процедуру на нескольких известных Вам простых и составных числах.
> Подсказка: удобный способ заставить \\(expmod\\) подавать особый сигнал — заставить ее возвращать \\(0\\).

На Scala эта программа будет выглядеть так:

```dotty
import scala.util.Random

def square(x: Long): Long = x * x

def expmod(base: Long, exp: Long, m: Long): Long =
  if exp == 0 then 1
  else if exp % 2 == 0 then
    val candidate = expmod(base, exp / 2, m)
    val root = square(candidate) % m
    if root == 1 && candidate != 1 && candidate != m - 1 then 0
    else root
  else (base * expmod(base, exp - 1, m)) % m

def fermatTest(n: Long): Boolean =
  def tryIt(a: Long): Boolean =
    expmod(a, n - 1, n) == 1
  tryIt(Random.nextLong(n - 1) + 1)

def fastIsPrime(n: Long, times: Int): Boolean =
  (times <= 0) || (fermatTest(n) && fastIsPrime(n, times - 1))

fastIsPrime(19, 100)   // true
fastIsPrime(199, 100)  // true
fastIsPrime(1999, 100) // true 

fastIsPrime(561, 100)  // false
fastIsPrime(1105, 100) // false
fastIsPrime(1729, 100) // false
fastIsPrime(2465, 100) // false
fastIsPrime(2821, 100) // false
fastIsPrime(6601, 100) // false
```

[Scala worksheet](https://scastie.scala-lang.org/DRqIItJmTxmmhIDoRYaTzw)


## 1.3. Формулирование абстракций с помощью процедур высших порядков

Процедура, принимающая другие процедуры как аргументы либо возвращающая их как значения, 
называется _процедурой высшего порядка_ (_higher-order procedure_).

### 1.3.1. Процедуры в качестве аргументов

Определим процедуру суммирования, принимающую другие процедуры в качестве аргументов.

```dotty
def cube(a: Double): Double = a * a * a

def sum(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  if a > b then 0.0
  else term(a) + sum(term, next(a), next, b)

def integral(f: Double => Double, a: Double, b: Double, dx: Double): Double =
  def addDx(x: Double): Double = x + dx
  sum(f, a + dx / 2, addDx, b) * dx

integral(cube, 0.0, 1.0, 0.01)  // 0.24998750000000042
integral(cube, 0.0, 1.0, 0.001) // 0.249999875000001
```

#### Упражнение 1.29

> Правило Симпсона — более точный метод численного интегрирования, чем представленный выше.
> С помощью правила Симпсона интеграл функции \\(f\\) между \\(a\\) и \\(b\\) приближенно вычисляется в виде
> \\(\frac{h}{3} * \[y\_{0} + 4y\_{1} + 2y\_{2} + 4y\_{3} + 2y\_{4} + ... + 2y\_{n-2} + 4y\_{n-1} + y\_{n}\]\\)
> , где \\(h = \frac{b - a}{n}\\), для какого-то четного целого числа \\(n\\), а \\(y\_{k} = f(a + kh)\\).
> (Увеличение \\(n\\) повышает точность приближенного вычисления.)
> Определите процедуру, которая принимает в качестве аргументов \\(f\\), \\(a\\), \\(b\\) и \\(n\\),
> и возвращает значение интеграла, вычисленное по правилу Симпсона.
> С помощью этой процедуры проинтегрируйте \\(cube\\) между \\(0\\) и \\(1\\) (с \\(n = 100\\) и \\(n = 1000\\))
> и сравните результаты с процедурой \\(integral\\), приведенной выше.


Решение на Scala:

```dotty
def simpsonRule(f: Double => Double, a: Double, b: Double, n: Int): Double =
  val h = (b - a) / n
  def y(k: Int): Double =
    val co = if k == 0 || k == n then 1 else if k % 2 == 0 then 2 else 4
    co * f(a + k * h)

  (0 to n).foldLeft(0.0)((acc, k) => acc + y(k)) * h / 3

simpsonRule(cube, 0.0, 1.0, 100)  // 0.25000000000000006   
simpsonRule(cube, 0.0, 1.0, 1000) // 0.25000000000000006
```

[Scala worksheet](https://scastie.scala-lang.org/4ZbXwD7YR7eMwKtOrLCALg)


#### Упражнение 1.30

> Процедура `sum` порождает линейную рекурсию.
> Ее можно переписать так, чтобы суммирование выполнялось итеративно.
> Покажите, как сделать это, заполнив пропущенные выражения в следующем определении:
>
> ```
> (define (sum term a next b)
>   (define (iter a result)
>      (if <??>
>          <??>
>          (iter <??> <??>)))
>   (iter <??> <??>))
> ```

Решение на Scala:

```dotty
def cube(a: Double): Double = a * a * a

def sum(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  def iter(a: Double, result: Double): Double =
    if a > b then result
    else iter(next(a), result + term(a))
  iter(a, 0.0)

def integral(f: Double => Double, a: Double, b: Double, dx: Double): Double =
  def addDx(x: Double): Double = x + dx
  sum(f, a + dx / 2, addDx, b) * dx

integral(cube, 0.0, 1.0, 0.01)  // 0.24998750000000042  
integral(cube, 0.0, 1.0, 0.001) // 0.24999987500000073
```

[Scala worksheet](https://scastie.scala-lang.org/MdvSkJvWT0qfjA9UgrGceg)


#### Упражнение 1.31

> а. Процедура \\(sum\\) — всего лишь простейшая из обширного множества подобных абстракций,
> которые можно выразить через процедуры высших порядков.
> Напишите аналогичную процедуру под названием \\(product\\),
> которая вычисляет произведение значений функции в точках на указанном интервале.
> Покажите, как с помощью этой процедуры определить \\(factorial\\).
> Кроме того, при помощи \\(product\\) вычислите приближенное значение \\(\pi\\) по формуле:
> \\(\frac{\pi}{4} = \frac{2}{3} * \frac{4}{3} * \frac{4}{5} * \frac{6}{5} * \frac{6}{7} * \frac{8}{7} * ...\\)
>
> б. Если Ваша процедура \\(product\\) порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный.
> Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.

Решение на Scala:

```dotty
val identity: Double => Double = x => x
val nextNum: Double => Double = x => x + 1
val square: Double => Double = x => x * x
val piFraction: Double => Double = k =>
  (2 * k) * (2 * k + 2) / square(2 * k + 1)
def productRec(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  if a > b then 1.0
  else term(a) * productRec(term, next(a), next, b)

def factorialRec(n: Int): Int =
  productRec(identity, 1, nextNum, n).toInt

factorialRec(10)     // 3628800     

def calculatePiRec(n: Int): Double =
  4 * productRec(piFraction, 1, nextNum, n)

calculatePiRec(1000) // 3.142377365093882  

def productIter(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  def iter(a: Double, result: Double): Double =
    if a > b then result
    else iter(next(a), result * term(a))
  iter(a, 1.0)

def factorialIter(n: Int): Int =
  productIter(identity, 1, nextNum, n).toInt

factorialIter(10)     // 3628800   

def calculatePiIter(n: Int): Double =
  4 * productIter(piFraction, 1, nextNum, n)

calculatePiIter(1000) // 3.1423773650938855
```

[Scala worksheet](https://scastie.scala-lang.org/csS3FdhYQxuUZC12CbgqrQ)

#### Упражнение 1.32

> а. Покажите, что **sum** и **product** (упражнение 1.31) являются частными случаями еще более общего понятия,
> называемого накопление (**accumulation**), которое комбинирует множество термов
> с помощью некоторой общей функции накопления **(accumulate combiner null-value term a next b)**
>
> **Accumulate** принимает в качестве аргументов те же описания термов и диапазона, что и **sum** с **product**,
> а еще процедуру **combiner** (двух аргументов), которая указывает,
> как нужно присоединить текущий терм к результату накопления предыдущих,
> и **null-value**, базовое значение, которое нужно использовать, когда термы закончатся.
> Напишите **accumulate** и покажите, как и **sum**, и **product** можно определить в виде простых вызовов **accumulate**.
>
> б. Если Ваша процедура **accumulate** порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный.
> Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный

Решение на Scala:

```dotty
def accumulateRec(
    combiner: (Double, Double) => Double,
    nullValue: Double,
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  if a > b then nullValue
  else
    combiner(
      term(a),
      accumulateRec(combiner, nullValue, term, next(a), next, b)
    )

def productRec(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  accumulateRec(_ * _, 1.0, term, a, next, b)

def accumulateIter(
    combiner: (Double, Double) => Double,
    nullValue: Double,
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  def iter(a: Double, result: Double): Double =
    if a > b then result
    else iter(next(a), combiner(result, term(a)))
  iter(a, nullValue)

def productIter(
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double
): Double =
  accumulateIter(_ * _, 1.0, term, a, next, b)
```

[Scala worksheet](https://scastie.scala-lang.org/DkL9dDr2S8aQdjwTs2p0OQ)

#### Упражнение 1.33

> Можно получить еще более общую версию **accumulate** (упражнение 1.32),
> если ввести понятие фильтра (**filter**) на комбинируемые термы.
> То есть комбинировать только те термы, порожденные из значений диапазона, которые удовлетворяют указанному условию.
>
> Получающаяся абстракция **filtered-accumulate** получает те же аргументы, что и **accumulate**,
> плюс дополнительный одноаргументный предикат, который определяет фильтр.
> Запишите **filtered-accumulate** в виде процедуры.
> Покажите, как с помощью **filtered-accumulate** выразить следующее:
>
> а. сумму квадратов простых чисел в интервале от **a** до **b**
> (в предположении, что процедура **prime?** уже написана);
>
> б. произведение всех положительных целых чисел меньше **n**,
> которые просты по отношению к **n** (то есть всех таких положительных целых чисел **i < n**, что **НОД(i, n) = 1**).

Решение на Scala:

```dotty
def filteredAccumulateRec(
    combiner: (Double, Double) => Double,
    nullValue: Double,
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double,
    filter: Double => Boolean
): Double =
  if a > b then nullValue
  else
    val nextA = term(a)
    lazy val res =
      filteredAccumulateRec(combiner, nullValue, term, next(a), next, b, filter)
    if filter(nextA) then combiner(nextA, res)
    else res

def filteredAccumulateIter(
    combiner: (Double, Double) => Double,
    nullValue: Double,
    term: Double => Double,
    a: Double,
    next: Double => Double,
    b: Double,
    filter: Double => Boolean
): Double =
  def iter(a: Double, result: Double): Double =
    if a > b then result
    else
      val nextA = term(a)
      val nextResult =
        if filter(nextA) then combiner(result, nextA)
        else result
      iter(next(a), nextResult)
  iter(a, nullValue)

def filteredAccumulate(
    combiner: (Int, Int) => Int,
    nullValue: Int,
    term: Int => Int,
    a: Int,
    next: Int => Int,
    b: Int,
    filter: Int => Boolean
): Int = ???

def isPrime(n: Int): Boolean = ???

def sumPrimeSquares(a: Int, b: Int): Int =
  filteredAccumulate(
    combiner = (x, y) => x + y,
    nullValue = 0,
    term = x => x * x,
    a = a,
    next = x => x + 1,
    b = b,
    filter = isPrime
  )

def gcd(a: Int, b: Int): Int = ???

def productPrimesLessThanN(n: Int): Int =
  filteredAccumulate(
    combiner = (x, y) => x * y,
    nullValue = 1,
    term = x => x,
    a = 1,
    next = x => x + 1,
    b = n - 1,
    filter = i => gcd(i, n) == 1
  )
```

[Scala worksheet](https://scastie.scala-lang.org/KXhnTQAvTeW7NsV9Wy3hRg)

### 1.3.2. Построение процедур с помощью lambda

Введем особую форму _**lambda**_, которая создает процедуры. 
С использованием lambda мы можем записать:

- (lambda (x) (+ x 4))
- (lambda (x) (/ 1.0 (* x (+ x 2))))

#### Упражнение 1.34

> Допустим, мы определили процедуру
>
> ```
> (define (f g)
>   (g 2))
> ```
>
> Тогда мы имеем
>
> ```
> (f square)
> 4
> ```
>
> ```
> (f (lambda (z) (* z (+ z 1))))
> 6
> ```
>
> Что случится, если мы (извращенно) попросим интерпретатор вычислить комбинацию **(f f)**?
> Объясните.

[Ссылка на объяснение](https://eli.thegreenplace.net/2007/07/13/sicp-sections-132-133)


### 1.3.3. Процедуры как обобщенные методы

##### Нахождение корней уравнений методом половинного деления

_Метод половинного деления_ (_half-interval method_) — это простой, но мощный способ
нахождения корней уравнения f(x) = 0, где f — непрерывная функция. 
Идея состоит в том, что если нам даны такие точки a и b, что f(a) < 0 < f(b),
то функция f должна иметь по крайней мере один ноль на отрезке между a и b. 
Чтобы найти его, возьмем x, равное среднему между a и b, и вычислим f(x). 
Если f(x) > 0, то f должна иметь ноль на отрезке между a и x. 
Если f(x) < 0, то f должна иметь ноль на отрезке между x и b.
Продолжая таким образом, мы сможем находить все более узкие интервалы, на которых f должна иметь ноль. 
Когда мы дойдем до точки, где этот интервал достаточно мал, процесс останавливается. 
Поскольку интервал неопределенности уменьшается вдвое на каждом шаге процесса, 
число требуемых шагов растет как Θ(log(L/T)), 
где L есть длина исходного интервала, а T есть допуск ошибки 
(то есть размер интервала, который мы считаем «достаточно малым»). 
Вот процедура, которая реализует эту стратегию:

```dotty
def average(a: Double, b: Double): Double =
  (a + b) / 2

val tolerance = 0.00001

def doesCloseEnough(a: Double, b: Double): Boolean =
  math.abs(a - b) < tolerance

def search(f: Double => Double, negPoint: Double, posPoint: Double): Double =
  val midpoint = average(negPoint, posPoint)
  if doesCloseEnough(negPoint, posPoint) then midpoint
  else 
    val testValue = f(midpoint)
    if testValue > 0 then search(f, negPoint, midpoint)
    else if testValue < 0 then search(f, midpoint, posPoint)
    else midpoint

search(identity, -1, 1) // 0.0
```

[Scala worksheet](https://scastie.scala-lang.org/UJDKNpuUTg2W6FTGCqS3hw)

Мы предполагаем, что вначале нам дается функция f и две точки, в одной из которых значение функции отрицательно, 
в другой положительно. Сначала мы вычисляем среднее между двумя краями интервала. 
Затем мы проверяем, не является ли интервал уже достаточно малым, и если да, сразу возвращаем среднюю точку как ответ. 
Если нет, мы вычисляем значение f в средней точке. 
Если это значение положительно, мы продолжаем процесс с интервалом от исходной отрицательной точки до средней точки.
Если значение в средней точке отрицательно, мы продолжаем процесс с интервалом от 
средней точки до исходной положительной точки. 
Наконец, существует возможность, что значение в средней точке в точности равно 0, 
и тогда средняя точка и есть тот корень, который мы ищем.

##### Нахождение неподвижных точек функций

Число x называется _неподвижной точкой_ (_fixed point_) функции f, если оно удовлетворяет уравнению f(x) = x. 
Для некоторых функций f можно найти неподвижную точку, начав с какого-то значения и применяя f многократно:
f(x), f(f(x)), f(f(f(x))), ... — пока значение не перестанет сильно изменяться. 
С помощью этой идеи мы можем составить процедуру fixed-point, которая в качестве аргументов принимает функцию и
начальное значение и производит приближение к неподвижной точке функции. 
Мы многократно применяем функцию, пока не найдем два последовательных значения, 
разница между которыми меньше некоторой заданной чувствительности:

```dotty
val tolerance = 0.00001

def fixedPoint(f: Double => Double, firstGuess: Double): Double =
  def doesCloseEnough(a: Double, b: Double): Boolean =
    math.abs(a - b) < tolerance
  def tryGuess(guess: Double): Double =
    val next = f(guess)
    if doesCloseEnough(next, guess) then next
    else tryGuess(next)
  tryGuess(firstGuess)
```

#### Упражнение 1.35

> Покажите, что золотое сечение \\(\varphi\\) (раздел 1.2.2)
> есть неподвижная точка трансформации \\(x → 1 + \frac{1}{x}\\),
> и используйте этот факт для вычисления \\(\varphi\\) с помощью процедуры \\(fixed-point\\).

\\(\varphi^{2} = \varphi + 1 => \varphi = 1 + \frac{1}{\varphi}\\)

Решение на Scala:

```dotty
fixedPoint(x => 1 + (1.0 / x), 1.0) // 1.6180327868852458
```

[Scala worksheet](https://scastie.scala-lang.org/kyMNERl5SnK8o9ePk1vrzg)

#### Упражнение 1.36

> Измените процедуру \\(fixed-point\\) так, чтобы она печатала последовательность приближений,
> которые порождает, с помощью примитивов \\(newline\\) и \\(display\\), показанных в упражнении 1.22.
> Затем найдите решение уравнения \\(x^{x} = 1000\\) путем поиска неподвижной точки \\(x → \frac{log(1000)}{log(x)}\\).
> (Используйте встроенную процедуру \\(Scheme log\\), которая вычисляет натуральные логарифмы.)
> Посчитайте, сколько шагов это занимает при использовании торможения усреднением и без него.
> (Учтите, что нельзя начинать \\(fixed-point\\) со значения \\(1\\), поскольку это вызовет деление на \\(log(1) = 0\\).)

Решение на Scala:

```dotty
def average(a: Double, b: Double): Double = (a + b) / 2

val tolerance = 0.00001

def fixedPoint(f: Double => Double, firstGuess: Double): Double =
  def doesCloseEnough(a: Double, b: Double): Boolean =
    math.abs(a - b) < tolerance
  def tryGuess(guess: Double): Double =
    val next = f(guess)
    println(next)
    if doesCloseEnough(next, guess) then next
    else tryGuess(next)
  tryGuess(firstGuess)

fixedPoint(x => math.log(1000) / math.log(x), 10.0)

fixedPoint(x => average(x, math.log(1000) / math.log(x)), 10.0)
```

В первом случае мы получаем такое приближение (33 итерации):

```text
res0: Double = 4.555532257016376
// 2.9999999999999996
// 6.2877098228681545
// 3.7570797902002955
// 5.218748919675316
// 4.1807977460633134
// 4.828902657081293
// 4.386936895811029
// 4.671722808746095
// 4.481109436117821
// 4.605567315585735
// 4.522955348093164
// 4.577201597629606
// 4.541325786357399
// 4.564940905198754
// 4.549347961475409
// 4.5596228442307565
// 4.552843114094703
// 4.55731263660315
// 4.554364381825887
// 4.556308401465587
// 4.555026226620339
// 4.55587174038325
// 4.555314115211184
// 4.555681847896976
// 4.555439330395129
// 4.555599264136406
// 4.555493789937456
// 4.555563347820309
// 4.555517475527901
// 4.555547727376273
// 4.555527776815261
// 4.555540933824255
// 4.555532257016376
```

Во втором - 9:

```text
res1: Double = 4.555536206185039
// 6.5
// 5.095215099176933
// 4.668760681281611
// 4.57585730576714
// 4.559030116711325
// 4.55613168520593
// 4.555637206157649
// 4.55555298754564
// 4.555538647701617
// 4.555536206185039
```

[Scala worksheet](https://scastie.scala-lang.org/GixzWz6oQRuj4BWMrbU4hw)

#### Упражнение 1.37

> а. Бесконечная цепная дробь (\\(continued fraction\\)) есть выражение вида
> \\(f = N\_{1} / (D\_{1} + N\_{2} / (D\_{2} + N\_{3} /(D\_{3} + ...)))\\)
> В качестве примера можно показать, что расширение бесконечной цепной дроби при всех \\(N\_{i}\\) и
> \\(D\_{i}\\), равных \\(1\\), дает \\(\frac{1}{\varphi}\\), где \\(\varphi\\) — золотое сечение (описанное в разделе 1.2.2).
> Один из способов вычислить цепную дробь состоит в том, чтобы после заданного количества термов оборвать вычисление.
> Такой обрыв — так называемая конечная цепная дробь (\\(finite continued fraction\\)) из \\(k\\) элементов, —
> имеет вид \\(f = N\_{1} / (D\_{1} + N\_{2} / (D\_{2} + N\_{3} / (D\_{3} + ... + N\_{k} / D\_{k})))\\).
> Предположим, что \\(n\\) и \\(d\\) — процедуры одного аргумента (номера элемента \\(i\\)),
> возвращающие \\(N\_{i}\\) и \\(D\_{i}\\) элементов цепной дроби.
> Определите процедуру \\(cont-frac\\) так, чтобы вычисление \\((cont-frac n d k)\\) давало значение \\(k\\)-элементной конечной цепной дроби.
> Проверьте свою процедуру, вычисляя приближения к \\(\frac{1}{\varphi}\\) с помощью
>
> ```
> (cont-frac (lambda (i) 1.0)
>            (lambda (i) 1.0)
>            k)
> ```
>
> для последовательных значений \\(k\\).
>
> Насколько большим пришлось сделать \\(k\\), чтобы получить приближение, верное с точностью 4 цифры после запятой?
>
> б. Если Ваша процедура \\(cont-frac\\) порождает рекурсивный процесс, напишите вариант, который порождает итеративный процесс.
> Если она порождает итеративный процесс, напишите вариант, порождающий рекурсивный процесс.

Для k == 11 точность составляет 4 знака.

Решение на Scala:

Рекурсивный процесс:

```dotty
def contFracRec(n: Int => Double, d: Int => Double, k: Int): Double =
  def loop(i: Int): Double =
    if i == k then n(i) / d(i)
    else n(i) / (d(i) + loop(i + 1))
  loop(1)

contFracRec(_ => 1.0, _ => 1.0, 11)
// res51: Double = 0.6180555555555556
```

Итеративный процесс:

```dotty
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
  def loop(i: Int, result: Double): Double =
    if i == 0 then result
    else loop(i - 1, n(i) / (d(i) + result))
  loop(k, 0.0)

contFracIter(_ => 1.0, _ => 1.0, 11)
// res53: Double = 0.6180555555555556
```

[Scala worksheet](https://scastie.scala-lang.org/o4M3kiklSiStzl3LUN91lg)

#### Упражнение 1.38

> В 1737 году швейцарский математик Леонард Эйлер опубликовал статью *De functionibus Continuis*,
> которая содержала расширение цепной дроби для `e−2`, где `e` — основание натуральных логарифмов.
> В этой дроби все \\(N\_{i}\\) равны `1`, а \\(D\_{i}\\) последовательно равны `1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...`
>
> Напишите программу, использующую Вашу процедуру `cont-frac` из упражнения 1.37
> для вычисления `e` на основании формулы Эйлера

Решение на Scala:

```dotty
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
  def loop(i: Int, result: Double): Double =
    if i == 0 then result
    else loop(i - 1, n(i) / (d(i) + result))
  loop(k, 0.0)

val n: Int => Double = _ => 1.0

val d: Int => Double = i =>
  if i % 3 == 2 then (i / 3 + 1) * 2
  else 1.0

contFracIter(n, d, 1000)
// res55: Double = 0.7182818284590453
```

[Scala worksheet](https://scastie.scala-lang.org/usu62Nt0TsqHQHYA97wZBA)

#### Упражнение 1.39

> Представление тангенса в виде цепной дроби было опубликовано в 1770 году немецким математиком Й.Х. Ламбертом:
>
> `tg x = x / (1 − x² / (3 − x² / (5 − ...)))`
>
> где `x` дан в радианах.
>
> Определите процедуру `(tan-cf x k)`, которая вычисляет приближение к тангенсу на основе формулы Ламберта.
> `K` указывает количество термов, которые требуется вычислить, как в упражнении 1.37.


Решение на Scala:

```dotty
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
  def loop(i: Int, result: Double): Double =
    if i == 0 then result
    else loop(i - 1, n(i) / (d(i) + result))
  loop(k, 0.0)

def n(x: Double)(i: Int): Double =
  if i == 1 then x
  else -x * x

val d: Int => Double = i => 2 * (i - 1) + 1

def tanCf(x: Double, k: Int): Double =
  contFracIter(n(x), d, k)

tanCf(1.0, 100)
// res57: Double = 1.557407724654902
```

[Scala worksheet](https://scastie.scala-lang.org/lZ9YXPg8S9ij3UZBAz8tUw)


### 1.3.4. Процедуры как возвращаемые значения

[Метод Ньютона описан в соответствующем разделе](../algorithms/algorithms/newton.md)

В общем случае языки программирования накладывают ограничения на способы, с
помощью которых можно манипулировать элементами вычисления. 
Говорят, что элементы, на которые накладывается наименьшее число ограничений, имеют статус элементов
вычисления _первого класса_ (_first-class_) или полноправных. 
Вот некоторые из их «прав и привилегий»:

- Их можно называть с помощью переменных.
- Их можно передавать в процедуры в качестве аргументов.
- Их можно возвращать из процедур в виде результата.
- Их можно включать в структуры данных.

#### Упражнение 1.40

> Определите процедуру `cubic`, которую можно было бы использовать совместно с процедурой `newtons-method`
> в выражениях вида `(newtons-method (cubic a b c) 1)` для приближенного вычисления нулей
> кубических уравнений \\(x^{3} + ax^{2} + bx + c\\).


Решение на Scala:

```dotty
def square(x: Double): Double = x * x

def cube(x: Double): Double = x * x * x

def cubic(a: Double, b: Double, c: Double): Double => Double = x =>
  cube(x) + a * square(x) + b * x + c
```

[Scala worksheet](https://scastie.scala-lang.org/y23lqOQTSgGCmR1FbPDKKw)


#### Упражнение 1.41

> Определите процедуру **double**, которая принимает как аргумент процедуру с одним аргументом
> и возвращает процедуру, которая применяет исходную процедуру дважды.
> Например, если процедура **inc** добавляет к своему аргументу **1**,
> то **(double inc)** должна быть процедурой, которая добавляет **2**.
>
> Скажите, какое значение возвращает **(((double (double double)) inc) 5)**


Решение на Scala:

```dotty
val inc: Int => Int = _ + 1

def double[T](f: T => T): T => T = x => f(f(x))

// (((double (double double)) inc) 5)
val f: (Int => Int) => (Int => Int) = double(double(double))
f(inc)(5) // 21
```

[Scala worksheet](https://scastie.scala-lang.org/GwhY4i7zTse1kU4xAw6LKQ)


#### Упражнение 1.42

> Пусть **f** и **g** — две одноаргументные функции.
> По определению, композиция (*composition*) **f** и **g** есть функция **x → f(g(x))**.
> Определите процедуру **compose** которая реализует композицию.
> Например, если **inc** — процедура, добавляющая к своему аргументу **1**,
>
> ```
> ((compose square inc) 6)
> 49
> ```


Решение на Scala:

```dotty
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))

val square: Int => Int = x => x * x
val inc: Int => Int = x => x + 1

compose(square, inc)(6) // 49
```

[Scala worksheet](https://scastie.scala-lang.org/hKt6WdQETDCLqfafsx7uHQ)


#### Упражнение 1.43

> Если `f` есть численная функция, а `n` — положительное целое число,
> то мы можем построить `n`-кратное применение `f`,
> которое определяется как функция, значение которой в точке `x` равно `f(f(... (f(x)) ...))`.
> Например, если `f` есть функция `x → x + 1`, то `n`-кратным применением `f` будет функция `x → x + n`.
> Если `f` есть операция возведения в квадрат,
> то `n`-кратное применение `f` есть функция, которая возводит свой аргумент в \\(2^{n}\\)-ю степень.
>
> Напишите процедуру, которая принимает в качестве ввода процедуру, вычисляющую `f`, и положительное целое `n`,
> и возвращает процедуру, вычисляющую `n`-кратное применение `f`.
>
> Требуется, чтобы Вашу процедуру можно было использовать в таких контекстах:
>
> ```
> ((repeated square 2) 5)
> 625
> ```
>
> Подсказка: может оказаться удобно использовать `compose` из упражнения 1.42

Решение на Scala:

```dotty
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))

def repeated[A](f: A => A, n: Int): A => A =
  if n == 1 then f
  else repeated(compose(f, f), n - 1)

val square: Int => Int = x => x * x
repeated(square, 2)(5) // 625
```

[Scala worksheet](https://scastie.scala-lang.org/YnKFqK1dTEaThXI09u1s1A)


#### Упражнение 1.44

> Идея сглаживания (*smoothing a function*) играет важную роль в обработке сигналов.
> Если `f` — функция, а `dx` — некоторое малое число, то сглаженная версия `f` есть функция,
> значение которой в точке `x` есть среднее между `f(x − dx)`, `f(x)` и `f(x + dx)`.
> Напишите процедуру `smooth`, которая в качестве ввода принимает процедуру, вычисляющую `f`,
> и возвращает процедуру, вычисляющую сглаженную версию `f`.
>
> Иногда бывает удобно проводить повторное сглаживание (то есть сглаживать сглаженную функцию и т.д.),
> получая `n`-кратно сглаженную функцию (*n-fold smoothed function*).
> Покажите, как породить `n`-кратно сглаженную функцию с помощью `smooth` и `repeated` из упражнения 1.43.


Решение на Scala:

```dotty
val dx: Double = 1e-6

def smooth(f: Double => Double): Double => Double =
  x => (f(x - dx) + f(x) + f(x + dx)) / 3

def nFoldSmoothedFunction(f: Double => Double, n: Int): Double => Double =
  repeated(smooth, n)(f)
```

[Scala worksheet](https://scastie.scala-lang.org/ofcf1izRRLKiYkw2dGP0zA)


#### Упражнение 1.45

> В разделе 1.3.3 мы видели, что попытка вычисления квадратных корней путем наивного поиска
> неподвижной точки \\(y → \frac{x}{y}\\) не сходится,
> и что это можно исправить путем торможения усреднением.
> Тот же самый метод работает для нахождения кубического корня как неподвижной точки \\(y → \frac{x}{y^{2}}\\),
> заторможенной усреднением.
> К сожалению, этот процесс не работает для корней четвертой степени — однажды примененного торможения усреднением недостаточно,
> чтобы заставить сходиться процесс поиска неподвижной точки \\(y → \frac{x}{y^{3}}\\).
> С другой стороны, если мы применим торможение усреднением дважды
> (т.е. применим торможение усреднением к результату торможения усреднением от \\(y → \frac{x}{y^{3}}\\)),
> то поиск неподвижной точки начнет сходиться.
> Проделайте эксперименты, чтобы понять, сколько торможений усреднением нужно,
> чтобы вычислить корень `n`-ой степени как неподвижную точку
> на основе многократного торможения усреднением функции \\(y → \frac{x}{y^{n-1}}\\).
> Используя свои результаты для написания простой процедуры вычисления корней `n`-ой степени с помощью процедур
> `fixed-point`, `average-damp` и `repeated` из упражнения 1.43.
> Считайте, что все арифметические операции, какие Вам понадобятся, присутствуют в языке как примитивы.

Судя по наблюдениям, для вычисления корней `n`-ой степени достаточно `log(n) + 1` торможений.

Решение на Scala:

```dotty
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))

def repeated[A](f: A => A, n: Int): A => A =
  if n == 1 then f
  else repeated(compose(f, f), n - 1)

def average(a: Double, b: Double): Double = (a + b) / 2

def averageDamp(f: Double => Double): Double => Double =
  x => average(x, f(x))

val tolerance = 1e-5

def fixedPoint(f: Double => Double, firstGuess: Double): Double =
  def doesCloseEnough(a: Double, b: Double): Boolean =
    math.abs(a - b) < tolerance
  def tryGuess(guess: Double): Double =
    val next = f(guess)
    if doesCloseEnough(next, guess) then next
    else tryGuess(next)
  tryGuess(firstGuess)

def nFoldAverageFunction(f: Double => Double, n: Int): Double => Double =
  repeated(averageDamp, n)(f)

def nRoot(x: Double, n: Int): Double =
  val f: Double => Double = y => (x / math.pow(y, n - 1))
  fixedPoint(nFoldAverageFunction(f, math.log(n).toInt + 1), 1.0)

nRoot(math.pow(2, 100), 100)
// res66: Double = 2.0079006560360497
```

[Scala worksheet](https://scastie.scala-lang.org/tm9BwnTRTJ2iFzNuzBVKDA)


#### Упражнение 1.46

> Некоторые из вычислительных методов, описанных в этой главе,
> являются примерами чрезвычайно общей вычислительной стратегии, называемой пошаговое улучшение (*iterative improvement*).
> Пошаговое улучшение состоит в следующем: чтобы что-то вычислить, нужно взять какое-то начальное значение,
> проверить, достаточно ли оно хорошо, чтобы служить ответом,
> и если нет, то улучшить это значение и продолжить процесс с новым значением.
>
> Напишите процедуру `iterative-improve`, которая принимает в качестве аргументов две процедуры:
> проверку, достаточно ли хорошо значение, и метод улучшения значения.
> `Iterative-improve` должна возвращать процедуру, которая принимает начальное значение в качестве аргумента
> и улучшает его, пока оно не станет достаточно хорошим.
>
> Перепишите процедуру `sqrt` из раздела 1.1.7 и
> процедуру `fixed-point` из раздела 1.3.3 в терминах `iterative-improve`.

Решение на Scala:

```dotty
def iterativeImprove(
    doesCloseEnough: (Double, Double) => Boolean,
    next: Double => Double
): Double => Double = firstGuess =>
  def tryGuess(guess: Double): Double =
    val nextGuess = next(guess)
    if doesCloseEnough(nextGuess, guess) then nextGuess
    else tryGuess(nextGuess)
  tryGuess(firstGuess)

def doesCloseEnough(a: Double, b: Double): Boolean =
  math.abs(a - b) < 1e-5

def average(x: Double, y: Double): Double = (x + y) / 2

def sqrt(x: Double): Double =
  iterativeImprove(doesCloseEnough, y => average(y, x / y))(1.0)

def fixedPoint(f: Double => Double, firstGuess: Double): Double =
  iterativeImprove(doesCloseEnough, f)(firstGuess)
```

[Scala worksheet](https://scastie.scala-lang.org/WyKYYyNVSBeB0tzxRl5t2Q)

---

**Ссылки:**

- [Abelson Harold, Sussman Gerald Jay, Sussman Julie - Structure and Interpretation of Computer Programs][SICP]
- [Почему в MIT больше не изучают SICP](https://habr.com/ru/articles/282986)
- [Eli Bendersky's solution](https://eli.thegreenplace.net/tag/sicp)
  
[SICP]: https://web.mit.edu/6.001/6.037/sicp.pdf
